Rerouting is important where a particular network router is in need of routine or immediate maintenance. Such maintenance may be implemented by a network system administrator, but it tedious and prone to errors in the rerouting procedure. Dynamic routing in an Internet Protocol (IP)-based communication network is typically accomplished by employing an Interior Gateway Protocol (IGP), such as an Open Shortest Path First (OSPF) routing protocol. The OSPF protocol is essentially an internetworking or gateway protocol that facilitates communications with external networks.
Routing is accomplished in the OSPF protocol by each network node having a routing database containing information related to network topology (e.g., links between network nodes). The routing database is utilized by each node to determine a path for transmitting a message to a destination site. The routing or path information is typically stored in a routing table. The routing databases are updated by exchanging link-state advertisement (LSA) packets between neighboring nodes. These packets generally include information related to current links of network nodes and are typically transferred periodically and/or in the event of a modification to the network topology. The OSPF protocol designates a particular router to flood LSA packets to neighbors in broadcast-type networks, while LSA packets are transmitted via point-to-point and/or broadcast packets within non-broadcast-type networks. Thus, the OSPF protocol is capable of ascertaining the topology of an IP communication network and determining routes to be used.
The OSPF protocol may further detect disabled communication links via periodic transmission and reception of neighbor discovery and maintenance or so-called “Hello” type packets between network nodes. These packets are periodically transmitted by each node to discover neighboring nodes and to ensure communication between that node and the neighboring nodes. In addition, the OSPF protocol may determine alternative routes for current routes that utilize disabled links and are no longer viable when a particular network node is removed from active service due to periodic or non-routine maintenance. However, the OSPF routing protocol suffers from several disadvantages.
In particular, this protocol takes a finite time interval to detect and repair a broken or disabled route. Although this is unavoidable in cases where the route becomes disabled due to an unforeseen event, protocol efficiency is less than optimal when a priori knowledge is available concerning network topology changes that affect viability of routes, for example, when a network node is scheduled for maintenance or upgrading. In this case, protocol efficiency may be enhanced by determining alternative routes prior to a network topology change.
OSPF is a widely used intra-domain routing protocol. It is also a link-state routing protocol, meaning that each router within the Autonomous System (AS) discovers and builds an entire view of the network topology. This topology view is conceptually a directed graph, in which each router represents a vertex in the topology graph, and each link between neighboring routers represents a unidirectional edge. Each link also has an associated weight that is administratively assigned in the configuration file of the router. Using the weighted topology graph, each router computes a shortest path tree with itself as the root, and applies the results to build its forwarding table. This assures that packets are forwarded along the shortest paths in terms of link weights to their destinations.
The computation of the shortest path tree is referred to herein as an SPF (Shortest Path First) computation, and the resultant tree is referred to as a Shortest-Path Tree (SPT). The OSPF topology can be divided into areas defining a two level hierarchy. Area 0, known as the backbone area, resides at the top level of the hierarchy and provides connectivity to the non-backbone areas (numbered 1, 2, . . . ). The OSPF protocol assigns each link to exactly one area.
Routers that have links to multiple areas are called border routers. A router maintains the complete topology graph of each area in which it has links. A router does not possess the entire topology of remote areas, but rather only has access to information regarding the total weight of paths from one or more border routers of its areas to each node in a remote area. OSPF allows routing information to be imported from other routing protocols like Border Gateway Protocol (BGP). The router that imports routing information from other protocols into OSPF is called an Autonomous System Border Router (ASBR).
OSPF performs SPF calculation in three stages. In the first stage, it calculates routes to intra-area destinations by computing SPTs for the topology graph of each area. This stage is referred to as the intra-area stage. In the second stage, it calculates routes to each remote node by selecting an appropriate border router as an intermediate node based on the path weight information. This stage is defined as the inter-area stage.
In the final stage, it calculates routes to each external node by selecting an appropriate ASBR as an intermediate node. This stage is referred to as the external stage. Routers running OSPF are responsible for describing local connectivity in a Link-State Advertisement (LSA). These LSAs are flooded reliably to all other routers in the network, which allows the remaining routers to build node-specific views of the topology. The set of LSAs in router memory is called a link-state database and conceptually forms the topology graph for the router.
The following discussion is proved as an overview of Internet Protocol (IP) addressing concepts. An IP address is a unique identifier for a node or host connection on an IP network. The IP address is a 32-bit binary number usually represented as four (4) decimal numbers, each decimal number representing eight (8) bits in the range of 0 to 255 (known as octets), which are separated by decimal points. This is known as “dotted decimal” notation. For example, 140.179.220.200 is an IP address, the binary form of which is as follows:                10001100.10110011.1101110.11001000.Typical values for default subnet masks are as follows:        Class A—255.0.0.0—11111111.00000000.00000000.00000000        Class B—255.255.0.0—11111111.11111111.00000000.00000000        Class C—255.255.255.0—11111111.1111111.111111.00000000        
IP addresses include two parts. One part identifies the network, and one part identifies the node. The Class of the address and the subnet mask determine which portion of the IP address belongs to the network address and which portion belongs to the node address.
Applying a subnet mask to an IP address enables the network and node portions of the address to be identified. The network bits are represented by 1's in the mask, and the node bits are represented by 0's. Performing a bitwise logical AND operation between the IP address and its subnet mask results in the Network Address or Number. For example, a bitwise logical AND operation performed between the binary form of the Class B IP address 140.179.240.200 and the binary form of the Default Class B subnet mask 255.255.0.0 results in a Network Address of 140.179.0.0, as follows:                10001100.10110011.11110000.11001000 (140.179.240.200)        11111111.11111111.00000000.00000000 (255.255.000.000)        10001100.10110011.00000000.00000000 (140.179.000.000)        
In accordance with Classless InterDomain Routing (CIDR), the subnet mask notation may be reduced to simplified shorthand. Specifically, rather than explicitly providing the bits of the subnet mask, the subnet mask is simply referred to by the number of 1's that start the mask. For example, rather than writing the address and subnet mask as “192.60.128.0, Subnet Mask 255.255.252.0”, the network address is simply represented by “192.60.128.0/22”, which indicates the starting address of the network, and the number of 1's, namely twenty-two (22), in the network portion of the address. A /22 subnet mask would be represented in binary form as follows:                11111111.11111111.11111100.00000000.        
The use of CIDR notation may also be used to represent a Classful address. For example the Class A subnet mask (255.0.0.0) may be referred to as a /8 subnet mask; the Class B subnet mask (255.255.0.0) may be referred to as a /16 subnet mask; and the Class C subnet mask (255.255.255.0) may be referred to as a /24 subnet mask.
OSPF and static routes support Variable-Length Subnet Masks (VLSMs). With VLSMs, different masks may be used for the same network number on different interfaces. For example, assuming a 30-bit subnet mask is used, two bits of address space are reserved for interface host addresses. This provides a sufficient host address space for two host endpoints on a point-to-point link.
Data networks, such as those maintained by communication service providers that perform any type of regular maintenance or upgrades on routable networks experience loss and delay of data packets due to routing re-convergence during maintenance. In addition, complex non-automated configuration changes are prone to human error. For instance, during manual cost changes, the time required for a typical router having about thirty-three (33) neighbors (New York backbone router) would take about one to two hours. Most of this time would be spent discovering the neighbors by relying on network maps, guesswork using local link IP addresses, and the like. Once the maintenance activity has been completed, the operator must manually note the current configured costs and restore them, in this instance, one by one, on thirty-three (33) neighbors (routers). In many instances, this manual procedure leads to incorrect or missed link cost configurations, and asymmetric cost restorations, which result in Plant Operator Error (POE) and an increase in Defects per Million (DPM).